/*
 *https://leetcode.cn/problems/numbers-with-repeated-digits/
 *1012. 至少有 1 位重复的数字
 *difficult 吴朝泽 2024.9.19
 *数位DP
 本题很类似 lc357，这道题要求的是至少有 1 位重复的数字个数，lc357 求的是每位数都不相同的数字个数
 例如在给定区间 [1,100] 中，至少有 1 位重复的数字有 10 个(11,22,33,44,55,66,77,88,99,100)
 而每位数都不相同的数恰好就是所有数减掉上面的 10 个数 (100 - 10 = 90)
*/


class Solution {
public:
    int arr[30];   //存储每一位的数字
    long long dp[30][1024];   //用于记忆化搜索，存储状态

    //pos 表示当前的位数，pre 表示上一位填的数字，flag 表示填的数字大小是否受到限制,bool 表示是否含有前导零
    long long DFS(int pos, int pre, bool flag, bool lead)
    {
        if(pos == 0)  return 1;

        //如果没有限制且前一位数有效，并且 dp[pos][pre] 已经被计算过就直接返回
        if(!flag && !lead && dp[pos][pre] != -1)  return dp[pos][pre];

        //判断最大的数可以是多少，如果 flag 不成立就是 0-9 都可以，否则当前位的数就是最大数
        int max_num = flag ? arr[pos] : 9;

        long long res = 0;
        for(int i = 0; i <= max_num; ++i)
        {
            if(i == 0 && lead)  
                res += DFS(pos-1, pre, flag && i == max_num, true);
            else
            {
                //这里使用位运算检测 i 是否被使用过，将 pre 和 1 << i 相与。
                //如果 pre 中的第 i 位是 1，那么结果就会非零，表示数字 i 已经被使用过
                if(pre & (1 << i))  continue;

                //将当前数字 i 的位添加到 pre 中。这样做是为了在下一层递归中记录数字 i 已被使用
                else  res += DFS(pos-1, pre | (1 << i), flag && i == max_num, lead && i == 0);
            }
        }
        if(!flag)  dp[pos][pre] = res;
        return res;
    }
  
    long long check(int x)
    {
        int n = x;
        int pos = 0;
        while(x)
        {
            arr[++pos] = x % 10;
            x /= 10;
        }
        return n+1 - DFS(pos, 0, 1, 1);    //与 lc357 的不同之处在这
    }

    int numDupDigitsAtMostN(int n)
    {
        memset(arr, 0, sizeof(arr));
        memset(dp, -1, sizeof(dp));
        return check(n);
    }
};